<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>排序算法实现</title>
</head>

<body>
    <script>
        class ArrayList {
            items = []

            //插入元素
            insert(item) {
                return this.items.push(item);
            }

            //调换位置
            transposition(m, n) {
                let temp = this.items[m];
                this.items[m] = this.items[n];
                this.items[n] = temp;
            }

            //冒泡排序:交换次数:O(n的平方).比较次数:O(n的平方)
            bubbleSort() {
                let length = this.items.length;
                for (let j = length - 1; j >= 0; j--) {
                    for (let i = 0; i < j; i++) {
                        if (this.items[i] > this.items[i + 1]) {
                            this.transposition(i, i + 1);
                        }
                    }
                }
            }

            //选择排序:交换次数:O(n).比较次数:O(n的平方)
            selectionSort() {
                for (let j = 0; j < this.items.length - 1; j++) {
                    //初始化最小值的下标
                    let min = j;
                    //每次都从后一个开始
                    for (let i = min + 1; i < this.items.length; i++) {
                        //如果出现比最小值还小的值,就记录最小值下标
                        if (this.items[min] > this.items[i]) {
                            //记录最小值下标
                            min = i;
                        }
                    }
                    //调换最小值的位置
                    this.transposition(min, j);
                }
            }

            //插入排序:
            insertionSort() {
                let length = this.items.length;
                //1.外层循环,从1的位置开始获取数据,向前面局部有序插入
                for (let i = 1; i < length; i++) {
                    //2.内层循环:获取i位置的元素,和前面的元素依次进行比较
                    let temp = this.items[i];
                    let j = i;
                    while (this.items[j - 1] > temp && j > 0) {
                        this.items[j] = this.items[j - 1];
                        j--;
                    }
                    //3.将最小的值放置到对应的位置
                    this.items[j] = temp;
                }

            }

            //希尔排序
            shellSort() {
                let length = this.items.length;
                //初始化增量,初识增量为数组长度的一半,以后每次增量减半取整,直到增量变为1
                let gap = Math.floor(length / 2);

                while (gap >= 1) {
                    //基于增量进行插入排序
                    for (let i = gap; i < length; i++) {
                        //保存取出将要与前面的值比较的值,方便赋值到前面的位置去
                        let temp = this.items[i];

                        let j = i;
                        //找到合适的位置,并进行替换,同时要注意,不能下标越界
                        while (this.items[j - gap] > temp && j > gap - 1) {
                            //把小的换到后面
                            this.items[j] = this.items[j - gap];
                            //根据增量进行变换,每个增量就是分组的标准,希尔排序就是多次按照这样的标准,从而达到提升效率的目的
                            j -= gap;
                        }
                        //把大的换到前面
                        this.items[j] = temp;
                    }
                    //改变增量
                    gap = Math.floor(gap / 2);
                }
            }

            //快速排序算法
            //1.选择枢纽
            median(left, right) {
                let center = Math.floor((left + right) / 2);

                //找出中位数
                if (this.items[left] > this.items[center]) {
                    this.transposition(left, center);
                }

                if (this.items[left] > this.items[right]) {
                    this.transposition(left, right);
                }

                if (this.items[center] > this.items[right]) {
                    this.transposition(center, right);
                }

                //将center换到right-1的位置
                this.transposition(center, right - 1);

                //返回中位数
                return this.items[right - 1]
            }
            //快速排序实现
            quickSort() {
                this.quick(0, this.items.length - 1);

            }
            //内部的递归函数
            quick(left, right) {
                //结束条件,如果left大于等于right的时候结束
                if (left >= right) return;
                //获取枢纽
                let pivot = this.median(left, right);

                //定义变量,记录当前找到的位置
                let i = left;
                let j = right - 1;

                //开始进行交换
                while (true) {
                    while (this.items[++i] < pivot) {}
                    while (this.items[--j] > pivot) {}
                    if (i < j) {
                        this.transposition(i, j);
                    } else {
                        break;
                    }
                }

                this.transposition(i, right - 1);

                this.quick(left, i - 1);
                this.quick(i + 1, right);
            }

            newQuickSort(array) {
                const sort = (arr, left = 0, right = arr.length - 1) => {
                    if (left >= right) { //如果左边的索引大于等于右边的索引说明整理完毕
                        return
                    }
                    let i = left
                    let j = right
                    const baseVal = arr[j] // 取无序数组最后一个数为基准值
                    while (i < j) { //把所有比基准值小的数放在左边大的数放在右边
                        while (i < j && arr[i] <= baseVal) { //找到一个比基准值大的数交换
                            i++
                        }
                        arr[j] = arr[i] // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
                        while (j > i && arr[j] >= baseVal) { //找到一个比基准值小的数交换
                            j--
                        }
                        arr[i] = arr[j] // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
                    }
                    arr[j] = baseVal // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
                    sort(arr, left, j - 1) // 将左边的无序数组重复上面的操作
                    sort(arr, j + 1, right) // 将右边的无序数组重复上面的操作
                }
                const newArr = array.concat() // 为了保证这个函数是纯函数拷贝一次数组
                sort(newArr)
                return newArr
            }

            //toString:打印当前数组的结果
            toString() {
                return this.items.join('-');
            }
        }

        let al = new ArrayList();
        al.insert(15);
        al.insert(8);
        al.insert(11);
        al.insert(13);
        al.insert(26);
        al.insert(98);
        al.insert(77);
        al.insert(369);
        al.insert(789);
        al.insert(1);
        al.insert(965);
        //添加的元素
        console.log('添加的元素:' + al.toString());

        //冒泡排序后
        //al.bubbleSort();
        //console.log('冒泡排序后:'+al.toString());

        //选择排序后
        /* al.selectionSort();
        console.log('选择排序后:'+al.toString()); */

        //插入排序后
        /* al.insertionSort();
        console.log('插入排序后:' + al.toString()); */

        //希尔排序
        /* al.shellSort();
        console.log('希尔排序后:' + al.toString()); */

        //快速排序(这个有bug)
        /* al.quickSort();
        console.log('快速排序后:' + al.toString()); */

        //这个快速排序,没bug
        console.log(al.newQuickSort(al.items));
    </script>
</body>

</html>